package 典型.动态规划;

// https://leetcode-cn.com/problems/chuan-di-xin-xi/
// 玩n次，到达节点p。玩n-1次，到达节点q+ p->q;  n 遍历-> q遍历（跳板）
public class LCP07 {
    public static void main(String[] args) {
    }
    public int numWays(int n, int[][] relation, int k) {
        int[][] dp = new int[k+1][n]; // dp[i][j]表示第i轮游戏，到达j编号的方案数量
        dp[0][0] = 1;
        for (int i = 1; i <= k; i++) {
            for (int[] ints : relation) {
                dp[i][ints[1]] += dp[i-1][ints[0]];
            }
        }
        return dp[k][n-1];
    }
}
